<h2>Problem 124</h2>
<div style="color:#666;font-size:80%;">14 July 2006</div><br />
<div class="problem_content">

<p>The radical of <i>n</i>, rad(<i>n</i>), is the product of distinct prime factors of <i>n</i>. For example, 504 = 2<img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 3<img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 7, so rad(504) = 2 <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 3 <img src='images/symbol_times.gif' width='9' height='9' alt='&times;' border='0' style='vertical-align:middle;' /> 7 = 42.</p>
<p>If we calculate rad(<i>n</i>) for <i>1</i> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <i>n</i> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 10, then sort them on rad(<i>n</i>), and sorting on <i>n</i> if the radical values are equal, we get:</p>
<table cellpadding='2' cellspacing='0' border='0' align='center'>
<tr>
<td colspan='2'><div style='text-align:center;'><b>Unsorted</b></div></td>
<td>&nbsp;</td>
<td colspan='3'><div style='text-align:center;'><b>Sorted</b></div></td>
</tr>
<tr>
<td><div style='text-align:center;'><img src='images/spacer.gif' width='50' height='1' alt='' /><br /><b><i>n</i></b></div></td>
<td><div style='text-align:center;'><img src='images/spacer.gif' width='50' height='1' alt='' /><br /><b>rad(<i>n</i>)</b></div></td>
<td><img src='images/spacer.gif' width='50' height='1' alt='' /><br /></td>
<td><div style='text-align:center;'><img src='images/spacer.gif' width='50' height='1' alt='' /><br /><b><i>n</i></b></div></td>
<td><div style='text-align:center;'><img src='images/spacer.gif' width='50' height='1' alt='' /><br /><b>rad(<i>n</i>)</b></div></td>
<td><div style='text-align:center;'><img src='images/spacer.gif' width='50' height='1' alt='' /><br /><b>k</b></div></td>
</tr>
<tr>
<td><div style='text-align:center;'>1</div></td><td><div style='text-align:center;'>1</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>1</div></td><td><div style='text-align:center;'>1</div></td><td><div style='text-align:center;'>1</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>2</div></td><td><div style='text-align:center;'>2</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>2</div></td><td><div style='text-align:center;'>2</div></td><td><div style='text-align:center;'>2</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>3</div></td><td><div style='text-align:center;'>3</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>4</div></td><td><div style='text-align:center;'>2</div></td><td><div style='text-align:center;'>3</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>4</div></td><td><div style='text-align:center;'>2</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>8</div></td><td><div style='text-align:center;'>2</div></td><td><div style='text-align:center;'>4</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>5</div></td><td><div style='text-align:center;'>5</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>3</div></td><td><div style='text-align:center;'>3</div></td><td><div style='text-align:center;'>5</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>6</div></td><td><div style='text-align:center;'>6</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>9</div></td><td><div style='text-align:center;'>3</div></td><td><div style='text-align:center;'>6</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>7</div></td><td><div style='text-align:center;'>7</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>5</div></td><td><div style='text-align:center;'>5</div></td><td><div style='text-align:center;'>7</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>8</div></td><td><div style='text-align:center;'>2</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>6</div></td><td><div style='text-align:center;'>6</div></td><td><div style='text-align:center;'>8</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>9</div></td><td><div style='text-align:center;'>3</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>7</div></td><td><div style='text-align:center;'>7</div></td><td><div style='text-align:center;'>9</div></td>
</tr>
<tr>
<td><div style='text-align:center;'>10</div></td><td><div style='text-align:center;'>10</div></td>
<td>&nbsp;</td>
<td><div style='text-align:center;'>10</div></td><td><div style='text-align:center;'>10</div></td><td><div style='text-align:center;'>10</div></td>
</tr>
</table>
<p>Let E(<i>k</i>) be the <i>k</i>th element in the sorted <i>n</i> column; for example, E(4) = 8 and E(6) = 9.</p>
<p>If rad(<i>n</i>) is sorted for 1 <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <i>n</i> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> 100000, find E(10000).</p>

</div><br />
